//模拟实现priority_queue类，并完成测试
#include<iostream>
#include<vector>
#include<functional>
using namespace std;
namespace bit
{
	template <class T, class Container = vector<T>, class Compare = less<T> >
	class priority_queue
	{
	private:
		void adjustup(int index)
		{
			int children = index;
			int parent = (index - 1) / 2;
			while ( comp(c[parent], c[children]))
			{
				swap(c[parent], c[children]);
				children = parent;
				parent = (children - 1) / 2;
			}
		}
		void adjustdown(int index)
		{
			int parent = index;
			int children = parent * 2 + 1;
			if (children + 1 < c.size() && comp(c[children], c[children + 1]))
			{
				children++;
			}
			while (children < c.size() && comp(c[parent], c[children]))
			{
				swap(c[parent], c[children]);
				parent = children;
				children = parent * 2 + 1;
				if (children + 1 < c.size() && comp(c[children], c[children + 1]))
				{
					children++;
				}
			}
		}
	public:

		priority_queue()
		{

		}

		template <class InputIterator>

		priority_queue(InputIterator first, InputIterator last)
		{
			InputIterator temp = first;
			while (temp != last)
			{
				push(*temp);
				temp++;
			}
		}

		bool empty() const
		{
			return c.empty();
		}

		size_t size() const
		{
			return c.size();
		}

		const T& top() const
		{
			if (empty()) {
				throw std::out_of_range("Priority queue is empty");
			}
			return c[0];
		}

		void push(const T& x)
		{
			c.push_back(x);
			adjustup(c.size() - 1);
		}

		void pop()
		{
			if (empty())
			{
				throw out_of_range("Priority queue is empty");
			}
			swap(c[0], c[c.size() - 1]);
			c.pop_back();
			adjustdown(0);
		}

	private:

		Container c;

		Compare comp;

	};

};

int main()
{
	bit::priority_queue<int,vector<int>,less<int>>arr;
	for (int i = 0; i < 100; i++)
	{
		arr.push(i);
	}
	int size = arr.size();
	for (int i = 0; i < size; i++)
	{
		cout << arr.top() << endl;
		arr.pop();
	}
	return 0;
}